The problem can be found at the following link: Question Link
To segregate the linked list containing 0s, 1s, and 2s, I'll follow the following steps:
- Traverse the linked list and count the occurrences of 0s, 1s, and 2s using a vector
cnt
. - Traverse the linked list again and replace the node data based on the count of 0s, 1s, and 2s.
- Time Complexity :
O(N)
, whereN
is the number of nodes in the linked list. - Auxiliary Space Complexity :
O(1)
, as we are using a fixed-size vector of length 3 to store the count of elements.
class Solution
{
public:
Node* segregate(Node* head)
{
vector<int> cnt(3, 0);
Node* itr = head;
// Count occurrences of 0s, 1s, and 2s
while (itr)
{
++cnt[itr->data];
itr = itr->next;
}
int i = 0;
itr = head;
// Replace node data based on counts
while (itr)
{
int c = 0;
while (c < cnt[i])
{
itr->data = i;
itr = itr->next;
++c;
}
++i;
}
return head;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.